# 快慢指针解题： 删除元素较少且靠前时，效率慢一些
class Solution:
    def removeElement(self, nums, val):

        n = len(nums)        
        i = j = 0

        while i < n:
            if nums[i] != val:
                nums[j] = nums[i]
                j += 1
            i += 1

        for i in range(j, n):
            nums.pop()

        return len(nums)



# 我写的对撞指针，模拟快速排序，从height 指针开始，到low指针。
class Solution:
    def removeElement(self, nums, val):

        n = len(nums)
        low = 0
        height = n - 1 

        while low < height:
            
            while nums[height] == val and low < height:
                height -= 1
            
            while nums[low] != val and low < height:
                low += 1
            
            if nums[low] == val and low < height:
                nums[low], nums[height] = nums[height], nums[low]

        for i in range(low + 1, n):
            nums.pop()

        if nums and nums[low] == val:
            nums.pop()
        
        return len(nums)


# 优化版（老师讲解的对撞指针）
class Solution:
    def removeElement(self, nums, val):

        n = len(nums)
        low = 0
        height = n - 1 

        if n == 0:
                return 0

        while low <= height:
            # 遇到要删除的元素，我是使用数组最以后一个元素替换这个元素
            # 替换后的数字有可能也是要删除的元素，那就接着判断，因为 low指针位置不变
            # 但是至少，我们从数组的最后删除了一个元素
            if nums[low] == val:
                nums[low] = nums[height]
                height -= 1
            else:
                low += 1

        return height + 1

nums = [3, 2, 2, 3]

s = Solution()
s.removeElement(nums, 3)